package problem211_Add_and_Search_Word;

public class WordDictionary {
	private TrieNode root;

	public WordDictionary() {
		root = new TrieNode();
	}

	// Adds a word into the data structure.
	public void addWord(String word) {
		char[] arr = word.toCharArray();
		TrieNode node = root;
		for (char c : arr) {
			int pos = c - 'a';
			if (node.sons[pos] == null)
				node.sons[pos] = new TrieNode(c);
			node = node.sons[pos];
		}
		node.isLeaf = true;
	}

	// Returns if the word is in the data structure. A word could
	// contain the dot character '.' to represent any one letter.
	public boolean search(String word) {
		char[] arr = word.toCharArray();
		return dfs(arr,root,0);
	}
	
	private boolean dfs(char[] arr,TrieNode node,int index){
		if(index==arr.length&&node.isLeaf)
			return true;
		else if(index>=arr.length)
			return false;
		char c=arr[index];
		if(c=='.'){
			for(int i=0;i<26;i++){
				if(node.sons[i]!=null){
					if(dfs(arr,node.sons[i],index+1)){
						return true;
					}
				}
			}
		}else if(c>='a'&&c<='z'){
			int pos=c-'a';
			if(node.sons[pos]!=null){
				return dfs(arr,node.sons[pos],index+1);
			}else{
				return false;
			}
		}
		return false;
	}
	
	public static void main(String[] args){
		WordDictionary wd=new WordDictionary();
		wd.addWord("a");
		System.out.println(wd.search("a"));
	}
}

class TrieNode {
	char val;
	TrieNode[] sons;
	boolean isLeaf;

	public TrieNode(char c) {
		val = c;
		sons = new TrieNode[26];
		isLeaf = false;
	}

	public TrieNode() {
		sons = new TrieNode[26];
		isLeaf=false; 
	}
}